package com.aqie.medium.string;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 791 自定义字符串排序
 * 未出现字符可以出现在任意位置
 * todo
 */
public class CustomSortString {
    /**
     * 重载的compare方法需要满足，自反性，对称性，和传递性
     * @param S
     * @param T
     * @return
     */
    public String customSortString(String S, String T) {
        char[] cs = T.toCharArray();
        Character ccs[] = new Character[cs.length];
        for (int i = 0;i < cs.length;i++) {
            ccs[i] = cs[i];
        }

        Arrays.sort(ccs, (a, b) -> {
            int indexA = S.indexOf(a);
            int indexB = S.indexOf(b);

            if (indexA < 0 && indexB < 0) {
                return 0;
            }

            if (indexA < 0 && indexB > 0) {
                return -1;
            }

            if (indexA > 0 && indexB < 0) {
                return 1;
            }

            if (indexA > indexB) {
                return 1;
            }


            if (indexA < indexB) {
                return -1;
            }

            if (indexA == indexB) {
                return 0;
            }

            return a > b ? 1 : a == b ? 0 : -1;
        });

        for (int i = 0;i < cs.length;i++) {
            cs[i] = ccs[i];
        }

        return new String(cs);


    }


    /**
     * 快速排序
     * @param args
     */
    String rule;
    public String customSortString2(String S, String T) {
        this.rule = S;
        char[] cs = T.toCharArray();
        quickSort(cs,0,cs.length - 1);
        return new String(cs);
    }

    private void quickSort(char[] sort,int left,int right) {
        if (left < right) {
            int pt = partition(sort,left,right);
            quickSort(sort,left,pt - 1);
            quickSort(sort,pt + 1,right);
        }
    }

    private int partition(char[] sort,int left,int right) {
        char temp = sort[left];

        while (left < right) {
            while (left < right && rule.indexOf(sort[right]) > rule.indexOf(temp)) {
                right--;
            }

            if (left < right) {
                sort[left] = sort[right];
                left++;
            }

            while (left < right && rule.indexOf(sort[left]) < rule.indexOf(temp)) {
                left++;
            }

            if (left < right) {
                sort[right] = sort[left];
                right--;
            }
        }

        sort[left] = temp;
        return left;
    }


    public static void main(String[] args) {
        String S = "cba";
        String T = "abcd";
    }

}
